package com.example.offer.no0013.impl;

import com.example.offer.no0013.Solution;

public class SolutionImpl implements Solution {

    private int[][] broad;
    private int m;
    private int n;
    private int k;

    @Override
    public int movingCount(int m, int n, int k) {
        broad = new int[m][n];
        this.m = m;
        this.n = n;
        this.k = k;
        return dfs(0, 0);
    }

    private int dfs(int i, int j) {
        if (i >= m || j >= n || broad[i][j] == 1 || (sum(i) + sum(j) > k)) {
            return 0;
        }
        broad[i][j] = 1;
        return 1 + dfs(i + 1, j) + dfs(i, j + 1);
    }

    private int sum(int num) {
        int sum = 0;
        while (num > 0) {
            sum = sum + num % 10;
            num = num / 10;
        }
        return sum;
    }
}
